<!DOCTYPE html>
<html lang="en">







<head>
 <script>(function(i,s,o,g,r,a,m){i["DaoVoiceObject"]=r;i[r]=i[r]||function(){(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;a.charset="utf-8";m.parentNode.insertBefore(a,m)})(window,document,"script",('https:' == document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/0eeeae6f.js","daovoice")
 daovoice('init', {
  app_id: "246e9537"
});
daovoice('update');
 </script>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/apple-touch-icon.png">
  <link rel="icon" type="image/png" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="description" content="">

  <meta name="author" content="xixilili">
  <meta name="keywords" content="">
  
  <title>背包问题最终总结 ~ xixilili.blog</title>
  <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/5.10.2/css/all.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.3.1/css/bootstrap.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/mdbootstrap/4.8.9/css/mdb.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/3.0.1/github-markdown.min.css"  >

<link rel="stylesheet" href="//at.alicdn.com/t/font_1067060_qzomjdt8bmp.css">



  <link rel="stylesheet" href="/lib/prettify/tomorrow-night.min.css"  >

<link rel="stylesheet" href="/css/main.css"  >


  <link rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css"  >


<meta name="generator" content="Hexo 4.2.0"></head>



<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>xixilili.blog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/">Home</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/archives/">Archives</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/categories/">Categories</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/tags/">Tags</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/about/">About</a>
          </li>
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background"
         style="background: url('https://capsule-1254369940.cos.ap-chengdu.myqcloud.com/xilixiliBg.jpg')no-repeat center center;
           background-size: cover;
           background-attachment: fixed;">
      <div class="full-bg-img">
        <div class="mask rgba-black-light flex-center">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              <br>
              
                <p class="mt-3">
                  <i class="fas fa-calendar-alt" aria-hidden="true"></i>&nbsp;
                  Sunday, April 19th 2020, 5:57 pm
                </p>
              

              <p>
                
                  
                  &nbsp;<i class="far fa-chart-bar"></i>
                  <span class="post-count">
                    5.1k 字
                  </span>&nbsp;
                

                
                  
                  &nbsp;<i class="far fa-clock"></i>
                  <span class="post-count">
                      22 分钟
                  </span>&nbsp;
                

                
                  <!-- 不蒜子统计文章PV -->
                  
                  &nbsp;<i class="far fa-eye" aria-hidden="true"></i>&nbsp;
                  <span id="busuanzi_container_page_pv">
                    <span id="busuanzi_value_page_pv"></span> 次
                  </span>&nbsp;
                
              </p>
            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      




<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="py-5 z-depth-3" id="board">
        <div class="post-content mx-auto" id="post">
          <div class="markdown-body">
            <h1 id="导语"><a href="#导语" class="headerlink" title="导语"></a>导语</h1><p>常见的背包问题有<br>1、组合问题：   dp[i] += dp[i-num]<br>2、True、False问题：dp[i] = dp[i] or dp[i-num]<br>3、最大最小问题：dp[i] = min(dp[i], dp[i-num]+1)<br>&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;dp[i] = max(dp[i], dp[i-num]+1)</p>
<p><font color=red><strong>注意dp的初始化!!!</strong></font></p>
<h1 id="0-1背包"><a href="#0-1背包" class="headerlink" title="0-1背包"></a>0-1背包</h1><h2 id="1-采药问题"><a href="#1-采药问题" class="headerlink" title="1.采药问题"></a>1.采药问题</h2><p><strong>题目描述</strong><br>辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”</p>
<p>如果你是辰辰，你能完成这个任务吗？</p>
<p><strong>输入格式</strong><br>第一行有2个整数T(1≤T≤1000)和M(1≤M≤100)，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。<br>接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。</p>
<p><strong>输出格式</strong><br>1个整数，表示在规定的时间内可以采到的草药的最大总价值。</p>
<p>输入输出样例<br><strong>输入</strong></p>
<blockquote>
<p>70 3<br>71 100<br>69 1<br>1 2</p>
</blockquote>
<p><strong>输出</strong> </p>
<blockquote>
<p>3</p>
</blockquote>
<p><strong>分析</strong><br>普通的0-1背包，求最大的收益</p>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;cstdio&gt;

using namespace std;
const int MAXN=1000;
int w[MAXN],v[MAXN];
int dp[MAXN];
int main(){
    int n,m;//容量为n,物品有m个
    cin&gt;&gt;n&gt;&gt;m;
    for(int i=1;i&lt;=m;i++){
        cin&gt;&gt;w[i]&gt;&gt;v[i];
    }
    for(int i=1;i&lt;=m;i++){//上到下,关于第i个物品选与不选
        for(int j=n;j&gt;=w[i];j--){//右到左，关于选与不选对应的收益
            dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
        }
    }
    cout&lt;&lt;dp[n]&lt;&lt;endl;
}
</code></pre>
<h2 id="2-装箱问题"><a href="#2-装箱问题" class="headerlink" title="2.装箱问题"></a>2.装箱问题</h2><p><strong>题目描述</strong><br>有一个箱子容量为V（200000≤V≤20000），同时有n个物品（300&lt;n≤30），每个物品有一个体积（正整数）。<br>要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。</p>
<p><strong>输入格式</strong><br>1个整数，表示箱子容量<br>1个整数，表示有n个物品<br>接下来n行，分别表示这n个物品的各自体积</p>
<p><strong>输出格式</strong><br>1个整数，表示箱子剩余空间。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>24 6<br>8<br>3<br>12<br>7<br>9<br>7</p>
</blockquote>
<p><strong>输出</strong> </p>
<blockquote>
<p>0</p>
</blockquote>
<p><strong>分析</strong><br>注意分析什么是模板中的变量的转换，比如什么是背包容量，什么是价值，什么是重量，这道题转化为求装入若干个物品使其体积和最大</p>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
const int MAXN=50;
int w[MAXN],v[MAXN];
int dp[30005];
int main(){
    int n,m;
    cin&gt;&gt;n&gt;&gt;m;
    for(int i=1;i&lt;=m;i++){
        cin&gt;&gt;w[i];
        v[i]=w[i];//这个题的物品重量等同于价值
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=n;j&gt;=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout&lt;&lt;n-dp[n]&lt;&lt;endl;
}
</code></pre>
<h2 id="3-最大约数和"><a href="#3-最大约数和" class="headerlink" title="3.最大约数和"></a>3.最大约数和</h2><p><strong>题目描述</strong><br>选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。</p>
<p><strong>输入格式</strong><br>输入一个正整数S。</p>
<p><strong>输出格式</strong><br>输出最大的约数之和。</p>
<p>输入</p>
<blockquote>
<p>11</p>
</blockquote>
<p>输出</p>
<blockquote>
<p>9</p>
</blockquote>
<p><strong>说明/提示</strong><br>取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。</p>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
const int MAXN=2000;
int v[MAXN];
int dp[10000];
int main(){
    int n,m;
    cin&gt;&gt;m;
    n=m;
    for(int i=1;i&lt;=m;i++){
        for(int j=1;j&lt;i;j++){
            if(i%j==0) v[i]+=j;
        }
        //cout&lt;&lt;i&lt;&lt;&quot;:&quot;&lt;&lt;v[i]&lt;&lt;endl;
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=n;j&gt;=i;j--){
            dp[j]=max(dp[j],dp[j-i]+v[i]);//数字本身为重量,数字的约数之和为价值
        }
    }
    cout&lt;&lt;dp[n]&lt;&lt;endl;
}</code></pre>
<h2 id="4-精卫填海"><a href="#4-精卫填海" class="headerlink" title="4.精卫填海"></a>4.精卫填海</h2><p><strong>题目描述</strong><br>发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》<br>精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？<br>事实上，东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。</p>
<p><strong>输入格式</strong><br>输入文件的第一行是三个整数：v、n、c。<br>从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。</p>
<p><strong>输出格式</strong><br>输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出’Impossible’（不带引号）。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>100 2 10<br>50 5<br>50 5</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>0</p>
</blockquote>
<p><strong>输入</strong></p>
<blockquote>
<p>10 2 1<br>50 5<br>10 2</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>Impossible</p>
</blockquote>
<p><strong>分析</strong><br>这道题稍微有点不同，这道题是算背包容量能剩下多少，所以在计算出各个dp后，要背包容量从1开始递增看是否能够满足，然后输出剩下的最大体力.</p>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
const int MAXN=10005;
int w[MAXN]; int v[MAXN];
int dp[20000];
int main(){
    int s,m,n;//s为剩下没填的体积,m为物品件数,n为背包容量
    cin&gt;&gt;s&gt;&gt;m&gt;&gt;n;
    for(int i=1;i&lt;=m;i++){
        cin&gt;&gt;v[i]&gt;&gt;w[i];
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=n;j&gt;=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//计算当前剩余体力能搬的最大体积数
        }
    }
    for(int i=1;i&lt;=n;i++){//遍历各个背包容量
        if(dp[i]&gt;=s) {cout&lt;&lt;n-i&lt;&lt;endl; return 0;}
    }
    //if(dp[n]&gt;=s) cout&lt;&lt;dp[n]-s&lt;&lt;endl; //错误，因为在之前就可能已经满足了，没求到剩下的最大体力
    cout&lt;&lt;&quot;Impossible&quot;&lt;&lt;endl;
    return 0;
}
</code></pre>
<h2 id="5-集合-Subset-Sums-组合数"><a href="#5-集合-Subset-Sums-组合数" class="headerlink" title="5.集合 Subset Sums(组合数)"></a>5.集合 Subset Sums(组合数)</h2><p><strong>题目描述</strong><br>对于从 1∼n 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果 n=3，对于{1,2,3} 能划分成两个子集合，每个子集合的所有数字和是相等的：{3} 和 {1,2} 是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果n=7，有四种方法能划分集合 {1,2,3,4,5,6,7}，每一种分法的子集合各数字和是相等的:</p>
<p>{1,6,7} 和 {2,3,4,5}<br>{2,5,7} 和 {1,3,4,6}<br>{3,4,7} 和 {1,2,5,6}<br>{1,2,4,7} 和 {3,5,6}</p>
<p>给出 n，你的程序应该输出划分方案总数。</p>
<p><strong>输入格式</strong><br>输入文件只有一行，且只有一个整数 n</p>
<p><strong>输出格式</strong><br>输出划分方案总数。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>7</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>4</p>
</blockquote>
<p><strong>分析</strong><br>方法类的背包问题，注意背包容量是总的和的一半，而最终求的是划分而不是集合，所以要除以2</p>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
const int MAXN=100;
long long dp[1000]={1};//方法种类的背包问题，初始化为1
int main(){
    int m,n;
    cin&gt;&gt;m;
    n=m;//n为物品数
    if((1+m)*m/2%2==0) m=(1+m)*m/2;//总的和，其一半是背包的容量
    else{
        cout&lt;&lt;0; return 0;
    }
    for(int i=1;i&lt;=n;i++){
        for(int j=m/2;j&gt;=i;j--){
            dp[j]=dp[j]+dp[j-i];//选与不选
        }
    }
    cout&lt;&lt;dp[m/2]/2&lt;&lt;endl;//因为求的是划分数而不是和为m/2的集合数
}
</code></pre>
<h2 id="6-目标和"><a href="#6-目标和" class="headerlink" title="6.目标和"></a>6.目标和</h2><p><img src="https://img-blog.csdnimg.cn/20200419174249875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>设P为正数集的和,N为负数集合的和,S为所有元素和,T为目标和<br>∵P+N=S<br>&ensp;&ensp;P-N=T<br>∴2P=S+T<br>所以只要找到在序列找到和为(S+T)/2的所有方案就行,此时转化成了0-1背包的组合数问题</p>
<pre><code class="cpp">class Solution {
public:
    int findTargetSumWays(vector&lt;int&gt;&amp; nums, int S) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i&lt;n;i++){
            sum+=nums[i];
        }
        long long temp=(long long)sum+(long long)S;
        if(temp%2==1||S-sum&gt;0) return 0;
        int target=(sum+S)/2;
        //初始化
        vector&lt;int&gt; dp(10010,0);
        dp[0]=1;;
        //cout&lt;&lt;dp[S]&lt;&lt;endl;
        for(int i=0;i&lt;n;i++){
            for(int j=target;j&gt;=nums[i];j--){
                //cout&lt;&lt;j&lt;&lt;&quot; &quot;&lt;&lt;j-nums[i]&lt;&lt;endl;
                dp[j]=dp[j]+dp[j-nums[i]];
                //cout&lt;&lt;dp[j]&lt;&lt;endl;
            }
        }
        return dp[target];
    }
};</code></pre>
<h2 id="7-分割等和子集-true-amp-false"><a href="#7-分割等和子集-true-amp-false" class="headerlink" title="7.分割等和子集(true&amp;false)"></a>7.分割等和子集(true&amp;false)</h2><p><img src="https://img-blog.csdnimg.cn/20200419170458826.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<pre><code class="cpp">class Solution {
public:

    long long dp[10010];

    bool canPartition(vector&lt;int&gt;&amp; nums) {
        int sum=0;
        for(int i=0;i&lt;nums.size();i++){
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        int target=sum/2;
        //初始化,注意初始化的方法
        vector&lt;bool&gt; dp(target,false);
        dp[0]=true;
        cout&lt;&lt;dp[0]&lt;&lt;endl;
        for(int i=0;i&lt;nums.size();i++){
            for(int j=target;j&gt;=nums[i];j--){
                dp[j]=dp[j]||dp[j-nums[i]];
                //cout&lt;&lt;dp[j]&lt;&lt;endl;
            }
        }
        return dp[target];
    }
};</code></pre>
<h2 id="8-一和零-双weight"><a href="#8-一和零-双weight" class="headerlink" title="8.一和零(双weight)"></a>8.一和零(双weight)</h2><p><img src="https://img-blog.csdnimg.cn/20200414182723147.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>注:这里的weight是二维的(对于每一个串都有自己0,1的weight)</p>
<pre><code class="cpp">    int findMaxForm(vector&lt;string&gt;&amp; strs, int m, int n) {
        //dp[i][j]表示i个0，j个1能够拼出的数组中的最大的字符串数量
        vector&lt;vector&lt;int&gt;&gt; dp(m+1,vector&lt;int&gt;(n+1));
        vector&lt;vector&lt;int&gt;&gt; weight(strs.size(),vector&lt;int&gt;(2,0));
        //cout&lt;&lt;dp[1][1]&lt;&lt;endl;
        for(int i=0;i&lt;strs.size();i++){
            for(int j=0;j&lt;strs[i].size();j++){
                if(strs[i][j]==&#39;0&#39;) weight[i][0]++;
                else weight[i][1]++;
            }
            //cout&lt;&lt;weight[i][0]&lt;&lt;&quot; &quot;&lt;&lt;weight[i][1]&lt;&lt;endl;
        }
        for(int k=0;k&lt;strs.size();k++){//从上到下每个物品选与不选
            //cout&lt;&lt;weight[k][0]&lt;&lt;&quot; &quot;&lt;&lt;weight[k][1]&lt;&lt;endl;
            for(int i=m;i&gt;=weight[k][0];i--){//遍历0的背包容量
                for(int j=n;j&gt;=weight[k][1];j--){//遍历1的背包容量
                    dp[i][j]=max(dp[i][j],dp[i-weight[k][0]][j-weight[k][1]]+1);
                    //cout&lt;&lt;dp[i][j]&lt;&lt;endl;
                }
            }
        }
        return dp[m][n];
    }</code></pre>
<h1 id="完全背包"><a href="#完全背包" class="headerlink" title="完全背包"></a>完全背包</h1><h2 id="1-疯狂的采药"><a href="#1-疯狂的采药" class="headerlink" title="1.疯狂的采药"></a>1.疯狂的采药</h2><p><strong>题目描述</strong><br>LiYuxiang是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”</p>
<p>如果你是LiYuxiang，你能完成这个任务吗？<br>此题和原题的不同点：<br>1.每种草药可以无限制地疯狂采摘。<br>2.药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！</p>
<p><strong>输入格式</strong><br>输入第一行有两个整数T（1 &lt;= T &lt;= 100000）和M（1 &lt;= M &lt;= 10000），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到10000之间（包括1和10000）的整数，分别表示采摘某种草药的时间和这种草药的价值。</p>
<p><strong>输出格式</strong><br>输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>70 3<br>71 100<br>69 1<br>1 2</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>140</p>
</blockquote>
<p><strong>分析</strong><br>完全背包要修改j的遍历方式，需要反着来</p>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
const int MAXN=10005;
int w[MAXN],v[MAXN];
int dp[100005];

int main(){
    int n,m;
    cin&gt;&gt;n&gt;&gt;m;
    for(int i=1;i&lt;=m;i++){
        cin&gt;&gt;w[i]&gt;&gt;v[i];
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=w[i];j&lt;=n;j++){//完全背包和0-1背包这里是反着的
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout&lt;&lt;dp[n]&lt;&lt;endl;
}
</code></pre>
<h2 id="2-神奇的四次方数"><a href="#2-神奇的四次方数" class="headerlink" title="2.神奇的四次方数"></a>2.神奇的四次方数</h2><p><strong>题目描述</strong><br>将一个整数m分解为n个四次方数的和的形式，要求n最小。例如，m=706,706=5^4+3^4,则n=2。</p>
<p><strong>输入格式</strong><br>一行，一个整数m。</p>
<p><strong>输出格式</strong><br>一行，一个整数n。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>706</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>2</p>
</blockquote>
<p><strong>分析</strong><br>这道题因为求的是最小，所以要将dp初始化为一个比较大的数，并且dp[0]=0；<br>相当于给一个初始值，含义为容量为0时最少选择0个数.</p>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;math.h&gt;
using namespace std;
const int MAXN=100;
int w[MAXN];//每个的w都是1
int dp[1000001];
int main(){
    //下面这两步一定要写
    memset(dp,63,sizeof(dp));
    //给了一个初始值，不然结果会是一个很大的数，其含义代表容量为0时最少选择0个数
    dp[0]=0;
    int n,m;//n为背包容量
    cin&gt;&gt;n;
    for(int i=1;pow(i,4)&lt;=n;i++){
        w[i]=i*i*i*i;
        m=i;//m表示物品的数目
    }
    for(int i=1;i&lt;=m;i++){
        for(int j=w[i];j&lt;=n;j++){//v[i]是1
            dp[j]=min(dp[j],dp[j-w[i]]+1);
//            cout&lt;&lt;dp[j]&lt;&lt;endl;
        }
    }
    cout&lt;&lt;dp[n]&lt;&lt;endl;
}
</code></pre>
<h2 id="3-零钱兑换-II-组合数"><a href="#3-零钱兑换-II-组合数" class="headerlink" title="3.零钱兑换 II(组合数)"></a>3.零钱兑换 II(组合数)</h2><p><img src="https://img-blog.csdnimg.cn/20200419161911317.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>是求组合数，因为{1,2},{2,1}是同一个<br>求组合数模板是<strong>先遍历物品，再遍历背包</strong></p>
<pre><code class="cpp">class Solution {
public:
    int dp[10010];
    int change(int amount, vector&lt;int&gt;&amp; coins) {
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i&lt;coins.size();i++){
            for(int j=coins[i];j&lt;=amount;j++){
                dp[j]=dp[j]+dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};</code></pre>
<h2 id="4-组合总和-Ⅳ-排列数-反向嵌套"><a href="#4-组合总和-Ⅳ-排列数-反向嵌套" class="headerlink" title="4.组合总和 Ⅳ(排列数,反向嵌套)"></a>4.组合总和 Ⅳ(排列数,反向嵌套)</h2><p><img src="https://img-blog.csdnimg.cn/20200419154823970.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NDQwODgy,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" alt="在这里插入图片描述"><br>是求排列数，因为{1,2},{2,1}不是同一个<br>求组合数模板是<strong>先遍历背包，再遍历物品</strong></p>
<pre><code class="cpp">class Solution {
public:
    int combinationSum4(vector&lt;int&gt;&amp; nums, int target) 
    {
        if(nums.size() == 0)
            return 0;

        vector&lt;unsigned int&gt; dp(target + 1, 0);
        dp[0] = 1;//组成0的方案只能是全部都不选择，所以方案数为1.

        for(int i = 0; i &lt;= target; i++)
        {
            for(int j = 0; j &lt; nums.size(); j++)
            {
                if(i - nums[j] &gt;= 0)
                    dp[i] += dp[i - nums[j]];
            }
        }

        return dp[target];
    }
};
</code></pre>
<h1 id="分组背包"><a href="#分组背包" class="headerlink" title="分组背包"></a>分组背包</h1><h2 id="1-通天之分组背包"><a href="#1-通天之分组背包" class="headerlink" title="1.通天之分组背包"></a>1.通天之分组背包</h2><p><strong>题目描述</strong><br>自01背包问世之后，小A对此深感兴趣。一天，小A去远游，却发现他的背包不同于01背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。</p>
<p><strong>输入格式</strong><br>两个数m,n，表示一共有n件物品，总重量为m<br>接下来n行，每行3个数ai,bi,ci，表示物品的重量，利用价值，所属组数</p>
<p><strong>输出格式</strong><br>一个数，最大的利用价值</p>
<p><strong>输入</strong></p>
<blockquote>
<p>45 3<br>10 10 1<br>10 5 1<br>50 400 2</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>10</p>
</blockquote>
<p><strong>分析</strong><br>分组背包采用结构体数组，其下标代表组数，内部的w，v数组存的是组内的元素情况，总组数要在输入中算出，第二次遍历也是先遍历所有组，其本质相当于0-1背包的问题</p>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
const int MAXN=2000;

struct group{
    int group_size;//组的大小
    int w[MAXN],v[MAXN];
}G[1000];//下标代表组号
int dp[10000];
int main(){
    int n,m,s=0;//s代表组数
    cin&gt;&gt;n&gt;&gt;m;
    for(int i=1;i&lt;=m;i++){
        int a,b,c;
        cin&gt;&gt;a&gt;&gt;b&gt;&gt;c;
        s=max(c,s);//统计总的组数
        G[c].group_size++;//c组内的成员增加
        int ci=G[c].group_size;
        G[c].w[ci]=a;
        G[c].v[ci]=a;
    }
    for(int i=1;i&lt;=s;i++){//从上到下遍历所有组
        for(int j=n;j&gt;=0;j--){
            for(int k=1;k&lt;=G[i].group_size;k++){//组内成员竞争，注意j不会变化
                if(j-G[i].w[k]&gt;=0){//注意
                    dp[j]=max(dp[j],dp[j-G[i].w[k]]+G[i].v[k]);
                }
            }
        }
    }
    cout&lt;&lt;dp[n]&lt;&lt;endl;
}
</code></pre>
<h2 id="2-金明的预算方案"><a href="#2-金明的预算方案" class="headerlink" title="2.金明的预算方案"></a>2.金明的预算方案</h2><p><strong>题目描述</strong><br>金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过NN元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：</p>
<p>主件 附件</p>
<p>电脑 打印机，扫描仪</p>
<p>书柜 图书</p>
<p>书桌 台灯，文具</p>
<p>工作椅 无</p>
<p>如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分5等：用整数1−5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。<br>请你帮助金明设计一个满足要求的购物单。</p>
<p><strong>输入格式</strong><br>第11行，为两个正整数，用一个空格隔开：</p>
<p>n m（其中N(&lt;32000)表示总钱数，m(&lt;60)为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j−1的物品的基本数据，每行有3个非负整数</p>
<p>v p q（其中v表示该物品的价格（v&lt;10000），p表示该物品的重要度（1-5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q&gt;0，表示该物品为附件，q是所属主件的编号）</p>
<p><strong>输出格式</strong><br>一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（&lt;200000）。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>1000 5<br>800 2 0<br>400 5 1<br>300 5 1<br>400 3 0<br>500 2 0</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>2200</p>
</blockquote>
<p><strong>分析</strong><br>先转化为分组问题，假设有主(①)，从(②)，从(③)<br>所以得到一个组内四个相斥的成员：<br>①、①②、①③、①③</p>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
const int MAXN=100;
struct group{
    int group_size;
    int w[MAXN],v[MAXN];
}G[2000];
int dp[32005];
//因为每个主件可以有0个、1个或2个附件,所以对于组内只有四种相互排斥的情况，所以可以转化为分组背包
int main(){
    int n,m;
    cin&gt;&gt;n&gt;&gt;m;
    for(int i=1;i&lt;=m;i++){
        int v,p,q;
        cin&gt;&gt;v&gt;&gt;p&gt;&gt;q;
        if(q==0){//是这组的第一个,i就代表了组号
            G[i].group_size=1;
            G[i].w[1]=v;
            G[i].v[1]=p*v;
        }
        else{
            if(G[q].group_size==1){//一主一从,q代表所从属的组
                G[q].group_size=2;
                G[q].w[2]=G[q].w[1]+v;//一个主，从一号
                G[q].v[2]=G[q].v[1]+p*v;
            }
            else{
                G[q].group_size=4;//
                G[q].w[3]=G[q].w[1]+v;//一个主，从二号
                G[q].v[3]=G[q].v[1]+p*v;
                G[q].w[4]=G[q].w[2]+v;//一个主，从一号，从二号
                G[q].v[4]=G[q].v[2]+p*v;
            }
        }
    }
    for(int i=1;i&lt;=m;i++){//遍历所有组
        for(int j=n;j&gt;=0;j--){
            for(int k=1;k&lt;=G[i].group_size;k++){//组内成员竞争
                if(j&gt;=G[i].w[k]){//
                    dp[j]=max(dp[j],dp[j-G[i].w[k]]+G[i].v[k]);
                    //cout&lt;&lt;dp[j]&lt;&lt;endl;
                }
            }
        }
    }
    cout&lt;&lt;dp[n]&lt;&lt;endl;

}
</code></pre>

            <hr>
          </div>
          <br>
          <div>
            <p>
            
              <span>
                <i class="iconfont icon-inbox"></i>
                
                  <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95">算法</a>
                  &nbsp;
                
              </span>&nbsp;&nbsp;
            
            
              <span>
                <i class="iconfont icon-tag"></i>
                
                  <a class="hover-with-bg" href="/tags/%E7%AE%97%E6%B3%95">算法</a>
                
                  <a class="hover-with-bg" href="/tags/c++">c++</a>
                
                  <a class="hover-with-bg" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92">动态规划</a>
                
              </span>
            
            </p>
            
              <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://zh.wikipedia.org/wiki/Wikipedia:CC_BY-SA_3.0%E5%8D%8F%E8%AE%AE%E6%96%87%E6%9C%AC" target="_blank" rel="nofollow noopener noopener">CC BY-SA 3.0协议</a> 。转载请注明出处！</p>
            
          </div>
        </div>
      </div>
    </div>
    <div class="d-none d-lg-block col-lg-2 toc-container">
      
  <div id="toc">
    <p class="h4"><i class="far fa-list-alt"></i>&nbsp;TOC</p>
    <div id="tocbot"></div>
  </div>

    </div>
  </div>
</div>

<!-- custom -->


<!-- Comments -->
<div class="col-lg-7 mx-auto nopadding-md">
  <div class="container comments mx-auto" id="comments">
    
      <br><br>
      
      
  <!--PC和WAP自适应版-->
  <div id="SOHUCS" sid='http://yoursite.com/2020/04/19/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93/'></div>
  <script type="text/javascript">
    (function () {
      var appid = 'cyuGAy6Y7';
      var conf = '';
      var width = window.innerWidth || document.documentElement.clientWidth;
      if (width < 960) {
        var head = document.getElementsByTagName('head')[0] || document.head || document.documentElement;
        var script = document.createElement('script');
        script.type = 'text/javascript';
        script.charset = 'utf-8';
        script.id = 'changyan_mobile_js';
        script.src = 'https://changyan.sohu.com/upload/mobile/wap-js/changyan_mobile.js?client_id=' + appid + '&conf=' + conf;
        head.appendChild(script);
      } else {
        var loadJs = function (d, a) {
          var c = document.getElementsByTagName('head')[0] || document.head || document.documentElement;
          var b = document.createElement('script');
          b.setAttribute('type', 'text/javascript');
          b.setAttribute('charset', 'UTF-8');
          b.setAttribute('src', d);
          if (typeof a === 'function') {
            if (window.attachEvent) {
              b.onreadystatechange = function () {
                var e = b.readyState;
                if (e === 'loaded' || e === 'complete') {
                  b.onreadystatechange = null;
                  a();
                }
              };
            } else {
              b.onload = a;
            }
          }
          c.appendChild(b);
        };
        loadJs('https://changyan.sohu.com/upload/changyan.js', function () {
          window.changyan.api.config({ appid: appid, conf: conf });
        });
      }
    })(); </script>


    
  </div>
</div>

    
  </main>

  
    <a class="z-depth-1" id="scroll-top-button" href="#" role="button">
      <i class="fa fa-chevron-up scroll-top-arrow" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  <footer class="mt-5">
  <div class="text-center py-3">
    <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><b>Hexo</b></a>
    <i class="iconfont icon-love"></i>
    <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"> <b>Fluid</b></a>
    <br>

    
  
    <!-- 不蒜子统计PV -->
    
    &nbsp;<span id="busuanzi_container_site_pv">总访问量 
          <span id="busuanzi_value_site_pv"></span> 次</span>&nbsp;
  
  
    <!-- 不蒜子统计UV -->
    
    &nbsp;<span id="busuanzi_container_site_uv">总访客数 
            <span id="busuanzi_value_site_uv"></span> 人</span>&nbsp;
  
  <br>



    


    <!-- cnzz Analytics icon -->
    

  </div>
</footer>

<!-- SCRIPTS -->
<script src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script src="https://cdn.staticfile.org/popper.js/1.15.0/umd/popper.min.js" ></script>
<script src="https://cdn.staticfile.org/twitter-bootstrap/4.3.1/js/bootstrap.min.js" ></script>
<script src="https://cdn.staticfile.org/mdbootstrap/4.8.9/js/mdb.min.js" ></script>
<script src="/js/main.js" ></script>


  <script src="/js/lazyload.js" ></script>



  
    <script src="https://cdn.staticfile.org/tocbot/4.8.0/tocbot.min.js" ></script>
  
  <script src="/js/post.js" ></script>



  <script src="https://cdn.staticfile.org/smoothscroll/1.4.10/smooth-scroll.min.js" ></script>



  <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>


<!-- Plugins -->


  
    <!-- Baidu Analytics -->
    <script>
      var _hmt = _hmt || [];
      (function () {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?6a61255581242c8c58471dfbffd3bd66# 百度统计的Key，参见 https://tongji.baidu.com/sc-web/10000033910/home/site/getjs?siteId=13751376 代码获取中 hm.js? 后边的字符串";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>
  

  

  

  

  <!-- cnzz Analytics -->
  



  <script src="https://cdn.staticfile.org/prettify/r298/prettify.min.js" ></script>
  <script>
    $(document).ready(function () {
      $('pre').addClass('prettyprint  linenums');
      prettyPrint();
    })
  </script>



  <script src="https://cdn.staticfile.org/typed.js/2.0.10/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "背包问题最终总结&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script src="https://cdn.staticfile.org/anchor-js/4.2.0/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "false",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      getSearchFile(path);
      this.onclick = null
    }
  </script>



  <script src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <script>
    $("#post img:not(.no-zoom img, img[no-zoom])").each(
      function () {
        var element = document.createElement("a");
        $(element).attr("data-fancybox", "images");
        $(element).attr("href", $(this).attr("src"));
        $(this).wrap(element);
      }
    );
  </script>





  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  



  <script>(function (i, s, o, g, r, a, m) {
      i['DaoVoiceObject'] = r;
      i[r] = i[r] ||
        function () {
          (i[r].q = i[r].q || []).push(arguments);
        };
      i[r].l = 1 * new Date();
      a = s.createElement(o);
      m = s.getElementsByTagName(o)[0];
      a.async = 1;
      a.src = g;
      a.charset = 'utf-8';
      m.parentNode.insertBefore(a, m);
    })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/246e9537.js", 'daovoice');
    daovoice('init', {
      app_id: "246e9537",
    });
    daovoice('update');
  </script>




<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginModelPath":"assets/","model":{"jsonPath":"/live2dw/assets/wanko.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"log":false,"pluginJsPath":"lib/","pluginRootPath":"live2dw/","tagMode":false});</script></body>
</html>
